package com.cty.C_SortAlgorithms.E_MergeSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/17 17:26
 * @Description: 归并排序  基于数组、递归实现
 * @version: 1.0
 */
public class MergeSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public MergeSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组尾部插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    /**
     * 将两个有序数组合并
     * @param workSpace
     * @param lowerBound
     * @param highPtr
     * @param upperBound
     */
    private void merge(DataItem[] workSpace, int lowerBound, int highPtr, int upperBound){
        int lowPtr = lowerBound;
        int mid = highPtr - 1;
        int num = upperBound - lowerBound + 1;
        int i = 0;

        while(lowPtr<=mid && highPtr<=upperBound)
            if(array[lowPtr].getKey() < array[highPtr].getKey())
                workSpace[i++] = array[lowPtr++];
            else
                workSpace[i++] = array[highPtr++];

        while(lowPtr <= mid)
            workSpace[i++] = array[lowPtr++];
        while(highPtr <= upperBound)
            workSpace[i++] = array[highPtr++];

        for(i=0; i<num; i++)
            array[lowerBound + i] = workSpace[i];
    }

    /**
     * 递归实现归并排序
     * @param workSpace
     * @param lowerBound
     * @param upperBound
     */
    private void recMergeSort(DataItem[] workSpace, int lowerBound, int upperBound){
        if(lowerBound != upperBound){
            int mid = (lowerBound + upperBound) / 2;
            recMergeSort(workSpace, lowerBound, mid);
            recMergeSort(workSpace, mid+1, upperBound);
            merge(workSpace, lowerBound, mid+1, upperBound);
        }
    }

    /**
     * 归并排序
     *      平均时间复杂度：  O(N*logN)    受数据分布影响不大
     *      最好情况：        O(N*logN)
     *      最坏情况：        O(N*logN)
     *      空间复杂度：      O(N)        需要额外空间辅助
     *      排序方式：                    外部排序
     *      稳定性：                      稳定
     * 分析：
     *      共有 log2(N)+1 层有序数组合并，每层比较次数在 N/2 ~ N，复制次数为 2*N；
     *      假设复制和比较是最费时的操作，递归的调用和返回不增加额外的开销，则：
     *          比较次数：(N/2 ~ N)*[log2(N)+1]
     *          复制次数：2*N*[log2(N)+1]
     */
    public void mergeSort(){
        DataItem[] workSpace = new DataItem[nItems];
        recMergeSort(workSpace, 0, nItems-1);
    }








    // 练习 归并排序


}  // end MergeSort{}
